<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>双向链表结构</title>
    * 既能能从头部遍历到尾部，又能从尾部遍历到头部
    * 也就是链表相连的过程是双向的
    * 实现原理是链表中的元素既有一个向前的引用，也有一个下一个的引用
</head>

<body>
    <script>
        class DoblyLinkedList {
            constructor() {
                this.length = 0
                this.head = null
                this.tail = null
                class Node {
                    constructor(data) {
                        this.data = data
                        this.next = null
                        this.prev = null
                    }
                }
            }
            append(data) {
                let nNode = new Node(data)
                if (this.length == 0) {
                    this.head = nNode
                    this.tail = nNode
                } else {
                    nNode.prev = this.tail
                    this.tail.next = nNode
                    this.tail = nNode
                }
                this.length += 1
            }
            insert(position, data) {
                if (position < 0 || position > this.length) return false
                let nNode = new Node(data)
                if (this.length == 0) {
                    this.head = nNode
                    this.tail = nNode
                } else {
                    if (position == 0) {
                        this.head.prev = nNode
                        nNode.next = this.head
                        this.head = nNode
                    } else if (position == this.length) {
                        nNode.prev = this.tail
                        this.tail.next = nNode
                        this.tail = nNode
                    } else {
                        let current = this.head
                        let index = 0
                        while (index++ < position) {
                            current = current.next
                        }
                        nNode.prev = current.prev
                        nNode.next = current
                        current.prev.next = nNode
                        current.prev = nNode
                    }
                }
                this.length += 1
            }
            get(position) {
                if (position < 0 || position >= this.length) return null
                let current = this.head
                let index = 0
                while (index++ < position) {
                    current = current.next
                }
                return current.data
            }
            indexOf(data) {
                let current = this.head
                let index = 0
                while (current) {
                    if (current.data == data) {
                        return index
                    }
                    current = current.next
                    index += 1
                }
                return -1
            }
            update(position, nData) {
                if (position < 0 || position >= this.length) return false
                let current = this.head
                let index = 0
                while (index++ < position) {
                    current = current.next
                }
                current.data = nData
                return true
            }
            removeAt(position) {
                if (position < 0 || position >= this.length) return null
                if (this.length == 1) {
                    this.head = null
                    this.tail == null
                    this.length -= 1
                    return null
                }
                if (position == 0) {
                    this.head.next.prev = null
                    this.head = this.head.next
                } else if (position == this.length - 1) {
                    this.tail.prev.next = null
                    this.tail = this.tail.prev
                } else {
                    let current = this.head
                    let index = 0
                    while (index++ < position) {
                        current = current.next
                    }
                    current.next.prev = current.prev
                    current.prev.next = current.next
                }
                this.length -= 1
                return current.data
            }
            remove(data) {
                let position = this.indexOf(data)
                return this.removeAt(position)
            }
            isEmpty() {
                return this.length == 0
            }
            size() {
                return this.length
            }
            getFirst() {
                return this.head.data
            }
            getLast() {
                return this.tail.data
            }
            backwardString() {
                let current = this.tail
                let str = ""
                while (current) {
                    str += current.prev + ""
                    current = current.prev
                }
                return str
            }
            forwardString() {
                let current = this.head
                let str = ""
                while (current) {
                    str += current.data + ""
                    current = current.next
                }
                return str
            }
            toString() {
                return this.forwardString()
            }
        }
    </script>
</body>

</html>